package array.nowcoder.easy;

import java.util.Scanner;

/**
 * @author bruin_du
 * @description 星际密码
 * https://www.nowcoder.com/questionTerminal/34f17d5f2a8240bea661a23ec095a062
 * @date 2022/5/23 15:48
 **/
public class InterstellarPassword {
    public static void main(String[] args) {
        int[] fibonacci = new int[10002];
        fibonacci[1] = 1;
        fibonacci[2] = 1;
        for (int i = 3; i < fibonacci.length; i++) {
            fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
            fibonacci[i] = fibonacci[i] % 10000;
        }
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int n = in.nextInt();
            int[] input = new int[n];
            for (int i = 0; i < input.length; i++) {
                input[i] = in.nextInt();
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < input.length; i++) {
                int index = input[i] + 1;
                //笨计算
//                int num = fibonacci[index];
//                if (num / 1000 != 0) {
//                    sb.append(num % 10000);
//                } else {
//                    StringBuilder tmp = new StringBuilder();
//                    tmp.append(num);
//                    for (int j = 0; j < 4 - tmp.length(); j++) {
//                        sb.append(0);
//                    }
//                    sb.append(num);
//                }

                //直接使用格式控制
                sb.append(String.format("%4d",fibonacci[index]));
            }
            System.out.println(sb);
        }
    }
}
